import java.util.Stack;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-01-16
 * Time: 22:59
 */
 class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
 }
 //二叉搜索树：左边节点值小于根节点的值，右边节点的值大于根节点的值
//根据这个规律，我们要找第k小的节点的值，那么也就是按照升序来找第k个值就行了，而中序遍历二叉搜索树就是升序的结果
//但是怎么依次输出这些值呢，我们知道中序遍历是左根右的顺序，最小的是最后一个访问的，但是必须又是第一个最小的值，所以借助栈来解决问题
public class Solution {
     //先把左子树全部入栈，最小的肯定在左子树上，然后寻找第k个元素，最后从弹出的节点里面让node去遍历右子树
     //跟递归的思想是差不多的
     int count = 0;//标记第k个小的节点数
     int ret=-1;
     public int KthNode(TreeNode proot, int k) {
         //迭代方法：
        /* if (proot == null || k <= 0) {
             return -1;
         }
         Stack<TreeNode> stack = new Stack<>();
         //放入根节点
         stack.push(proot);
         //用于遍历搜索树
         TreeNode cur = proot;
         int i = 0;//用于找到第k小的节点，直到把所有的左子树节点入栈，那么就一定会找到一个最小的，就是第一小的，会弹出的，那么就先让i++
         while (!stack.isEmpty()) {
             //不断遍历左子树,将左子树节点加入到栈中
             while (cur.left != null) {
                 stack.push(cur.left);
                 cur = cur.left;
             }
             //开始找第k小的元素
             i++;
             if(i==k) return stack.pop().val;
             TreeNode tmp = stack.pop();
             //开始找弹出的右子树
             if (tmp.right != null) {
                 stack.push(tmp.right);
                 cur = tmp.right;
             }
         }
         return -1;*/
         //递归方法：
         if(proot==null || k<=0){
             return -1;
         }
         //左子树
         KthNode(proot.left,k);
         count++;
         //找节点
         if(count==k){
             return ret= proot.val;
         }
         //右子树
         KthNode(proot.right,k);
         //返回值
         return  ret;
     }
 }